/**
 * @program: data_structures_algorithms
 * @description: 指针交换法
 * @author: lld
 * @create: 2020-11-01 20:08
 **/
public class QuickSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件：startIndex大等于endIndex的时候
        if (startIndex >= endIndex) {
            return;
        }
// 得到基准元素位置
//        int pivotIndex = partition(arr, startIndex, endIndex);
        int pivotIndex = partition1(arr, startIndex, endIndex);
// 根据基准元素，分成两部分递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * @Description: 双边循环法
     * @Param: [arr, startIndex, endIndex]
     * @return: int
     **/
    private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right) {
//控制right指针比较并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
//控制left指针比较并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
//交换left和right指向的元素
            if (left < right) {
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;
            }
        }
//pivot和指针重合点交换
        int p = arr[left];
        arr[left] = arr[startIndex];
        arr[startIndex] = p;
        return left;
    }
/**
* @Description: 单循环法
* @Param: [arr, startIndex, endIndex]
* @return: int
**/
    private static int partition1(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;//首先指针指向第一个元素
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {//小于基准元素，指针右移，交换指针位和arr[i]的值
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;

            }
        }
        arr[startIndex] = arr[mark];//交换基准和mark的值
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
//        quickSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
        //测试执行效率
        int[] bigArray1 = new int[10000000];
        for (int i = 0; i < bigArray1.length; i++) {
            bigArray1[i] = (int) (Math.random() * 1000000000);
        }
        long start = System.currentTimeMillis();
        quickSort(bigArray1, 0, bigArray1.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("10000000个数据排序时间(毫秒):" + (end - start));//双1500，单1400
    }
}
